package problem239;

//239.滑动窗口最大值
//https://leetcode.cn/problems/sliding-window-maximum/?envType=study-plan-v2&envId=top-100-liked
//优先级队列
import java.util.PriorityQueue;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int maxVal = 0, count = 0;
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b)->{
            if(a[0] == b[0]) return b[1]-a[1];
            else return b[0] - a[0];
        });

        int[] ret = new int[n-k+1];
        int index = 0;
        for(int i = 0; i<k; i++) {
            queue.add(new int[]{nums[i], i});
        }
        ret[index++] = queue.peek()[0];
        for(int i = k; i<n; i++) {
            queue.add(new int[]{nums[i],i});
            while(queue.peek()[1] <= i - k) {
                queue.poll();
            }
            ret[index++] = queue.peek()[0];
        }
        return ret;
    }
}